public class D_aryHeapSort {
	public int[] data;
	  
	public D_aryHeapSort(int[] data){
		this.data=data;
	}
	
	public static void main(String[] args) {  
        int[] data5 = new int[] {10 ,-5, 3, 6, 2, 1, 9, 4, 8, 7,-1,100 ,-2};  
        print(data5); 
        D_aryHeapSort sort=new D_aryHeapSort(data5);
        //heapSort(data5,3); 
        sort.insert(14,3);
        System.out.println("排序后");
        print(sort.data);
   
    }  
  
    public void swap(int[]data,int i, int j) {  
        if (i == j) {  
            return;  
        }  
        data[i] = data[i] + data[j];  
        data[j] = data[i] - data[j];  
        data[i] = data[i] - data[j];  
    }  
  
    public void heapSort(int[] data,int d) {  
        for (int i = 0; i < data.length; i++) {  
            createMaxdHeap(data, data.length - 1 - i,d);  
            swap(data,0, data.length - 1 - i);  
           // print(data);  
        }  
    }  
  
    public void createMaxdHeap(int[] data, int lastIndex,int d) {  
        for (int i = lastIndex/d; i >= 0; i--) {  
            // 保存当前正在判断的节点  
            int k = i;  
           // System.out.println("k="+k);
            // 若当前节点的子节点存在  
            while(d * k + 1 <=lastIndex) {  
                // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点  
                int initIndex = d * k + 1;  
                int maxIndex=initIndex;
                for(int j=initIndex;j<=initIndex+d;j++){     	
	                if (j<=lastIndex)  
	                    // 若右子节点存在，否则此时biggerIndex应该等于 lastIndex  
	                    if (data[maxIndex] < data[j])  
	                        // 若右子节点值比左子节点值大，则biggerIndex记录的是右子节点的值  
	                    	maxIndex=j; 
                }
                    if (data[k] < data[maxIndex]) {  
                    // 若当前节点值比子节点最大值小，则交换2者得值，交换后将biggerIndex值赋值给k  
                        swap(data,k, maxIndex);  
                        k=maxIndex;  
                    } else {  
                       break;  
                     } 
                   // System.out.println("maxindex="+maxIndex);
                }
            }          
    }
    
    /*
     * 数组data的传值问题
     */
   public  void insert(int e,int d){
	   int[] temp=new int[data.length+1];
	   for(int i=0;i<data.length;i++)
		   temp[i]=data[i];
	   temp[temp.length-1]=e;   
	   heapSort(temp,d); 
	   data=new int[temp.length];
	   //for(int i=0;i<temp.length;i++)
		//   data[i]=temp[i];
	   data=temp;
	   System.out.println("paixuhou");
	   print(data);
   }
    
    public static void print(int[] data) {  
        for (int i = 0; i < data.length; i++) {  
            System.out.print(data[i] + "\t");  
        }  
        System.out.println();  
    }  
  
}  

